//93. 复原IP地址

/**
 * @param {string} s
 * @return {string[]}
 */

var restoreIpAddresses = function(s) {
    let ans = []
    if(s.length>12) return ans
    let set = dfs(s,0,4)
    if(set!==null){
        for (const it of set) {
            ans.push(it)
        }
    }
    return ans
};

function isValid(s){
    return s.length===1||(s.length===2&&s.charAt(0)!=='0')||(s.length===3&&s*1<=255&&s.charAt(0)!=='0')
}

function dfs(s,start,n){
    if(start>=s.length){
        if(n===0) return  ['']
        return null
    }
    let list = new Set()
    let list1 = dfs(s,start+1,n-1)
    if(list1!==null){
        let s1 = s.substring(start,start+1)
        for (const it of list1) {
            if(it!==''){
                list.add(s1+'.'+it)
            }else{
                list.add(s1+it)
            }
            
        }
    }
    let s2 = s.substring(start,start+2)
    if(isValid(s2)){
        list1 = dfs(s,start+2,n-1)
        if(list1!==null){
        for (const it of list1) {
            if(it!==''){
                list.add(s2+'.'+it)
            }else{
                list.add(s2+it)
            }
            
        }
    }
    }
    let s3 = s.substring(start,start+3)
    if(isValid(s3)){
        list1 = dfs(s,start+3,n-1)
        if(list1!==null){
            for (const it of list1) {
                if(it!==''){
                    list.add(s3+'.'+it)
                }else{
                    list.add(s3+it)
                }
            }
        }
    }
    return list
}

